function shellSort(arr) {
  const n = arr.length;

  // 初始间隔（gap）为数组长度的一半，逐步缩小间隔
  for (let gap = Math.floor(n / 2); gap > 0; gap = Math.floor(gap / 2)) {
    // 对每个子序列进行插入排序
    for (let i = gap; i < n; i++) {
      const temp = arr[i]; // 当前待插入的元素
      let j;

      // 在子序列中寻找插入位置
      for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
        arr[j] = arr[j - gap]; // 将较大的元素向后移动
      }

      // 插入待排序元素
      arr[j] = temp;
    }
  }

  return arr;
}

// 示例
const arr = [9, 8, 3, 7, 5, 6, 4, 1];
console.log(shellSort(arr)); // 输出: [1, 3, 4, 5, 6, 7, 8, 9]